A network security application may monitor network devices on a network to attempt to detect whether any network device has been infected with a malicious application, such as a virus or a malware. Once a malicious application is detected, the network security application may prevent the network application from executing on the network device.
One method for detecting malicious applications employs the use of a relatively large security dataset organized into a base graph having vertices (also called nodes) connected by edges. Because of the relatively large security dataset, the corresponding base graph may also be relatively large. Therefore, to reduce the overall size of a base graph, in order to improve computational efficiency, the base graph may be perturbed. Perturbing a base graph may be accomplished by adding or deleting edges, collapsing nodes into supernodes, or collapsing edges into superedges.
Graph summarization is a specific graph perturbing technique where nodes are collapsed into supernodes and multiple edges are combined into superedges in order to form a more concise version of a larger, original graph.
Unfortunately, however, after a certain point graph summarization may affect the utility of a graph for a network security application because data is lost during graph summarization.
The subject matter claimed herein is not limited to embodiments that solve any disadvantages or that operate only in environments such as those described above; rather, this background is only provided to illustrate one example technology area where some embodiments described herein may be practiced.